//1.二维dp--先解决小问题，再逐步推到大问题。
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

//2.优化后，一维dp，空间大优化
/*
在一维数组更新的过程中：
dp[j]（更新前） 还没被覆盖时，它保存的是上一行的 dp[i-1][j]。 → 对应二维 DP 的“上方”。

dp[j-1]（更新后） 已经在当前行更新过了，所以它保存的是 dp[i][j-1]。 → 对应二维 DP 的“左边”。

prev 我们手动保存的变量，存的是更新前的 dp[j-1]，也就是上一行的 dp[i-1][j-1]。 → 对应二维 DP 的“左上角”。
*/
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
    if (text1.size() < text2.size()) swap(text1, text2);   //能保证一维数组的长度最小，节省内存，比如text1=10, text2=1000 时
    int m = text1.size(), n = text2.size();
    vector<int> dp(n + 1, 0);

    for (int i = 1; i <= m; i++) {
        int prev = 0; // 相当于 dp[i-1][j-1]
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (text1[i - 1] == text2[j - 1]) {
                dp[j] = prev + 1; // 相当于 dp[i-1][j-1] + 1
            } else {
                dp[j] = max(dp[j], dp[j - 1]); // 相当于 max(dp[i-1][j], dp[i][j-1])
            }
            prev = temp;
        }
    }
    return dp[n];
    }

};
//3.dfs+记忆化搜索--大问题拆成小问题
class Solution {
public:
    int m, n;
    vector<vector<int>> memo;

    int dfs(string& s1, string& s2, int i, int j) {
        if (i == m || j == n) return 0;
        if (memo[i][j] != -1) return memo[i][j];

        if (s1[i] == s2[j]) {
            return memo[i][j] = 1 + dfs(s1, s2, i+1, j+1);
        } else {
            return memo[i][j] = max(dfs(s1, s2, i+1, j), dfs(s1, s2, i, j+1));
        }
    }

    int longestCommonSubsequence(string text1, string text2) {
        m = text1.size(); n = text2.size();
        memo.assign(m, vector<int>(n, -1));
        return dfs(text1, text2, 0, 0);
    }
};
